//Given the head of a singly linked list, return true if it is a palindrome. 
//
// 
// Example 1: 
//
// 
//Input: head = [1,2,2,1]
//Output: true
// 
//
// Example 2: 
//
// 
//Input: head = [1,2]
//Output: false
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the list is in the range [1, 105]. 
// 0 <= Node.val <= 9 
// 
//
// 
//Follow up: Could you do it in O(n) time and O(1) space? Related Topics 栈 递归 链表
// 双指针 
// 👍 1128 👎 0


package leetcode.editor.cn;

//Java：Palindrome Linked List
class P234PalindromeLinkedList {
    public static void main(String[] args) {
        Solution solution = new P234PalindromeLinkedList().new Solution();
        // TO TEST
        ListNode root = new ListNode(1);
        root.next = new ListNode(2);
        root.next.next = new ListNode(2);
        root.next.next.next = new ListNode(1);
        System.out.println(solution.isPalindrome(root));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        ListNode root;

        public boolean isPalindrome(ListNode head) {
            ListNode root = head;
            int size = 0;
            while (root != null) {
                root = root.next;
                size++;
            }
            int mid = size % 2 == 0 ? size / 2 : size / 2 + 1;
            size = 0;
            ListNode fast = head;
            while (size++ < mid) {
                fast = fast.next;
            }
            fast = reverseNode(fast);
            while (fast != null) {
                if (fast.val == head.val) {
                    fast = fast.next;
                    head = head.next;
                } else {
                    return false;
                }
            }
            return true;
        }

        public ListNode reverseNode(ListNode root) {
            ListNode pre = null;
            ListNode cur = root;
            ListNode next;
            while (cur != null) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}